/*
 * MCR.cpp
 *
 *  Created on: Sep 19, 2011
 *      Author: correa
 */
/*******************************************************************************************************************************
 * Solving the maximum stable set problem using the algorithm described in
 *
 * E. Tomita and T. Kameda
 * An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
 * Journal of Global Optimization, 2007, 37:1, pages 95--111
 * http://dx.doi.org/10.1007/s10898-006-9039-7
 *
 * Parallel
 * --------
 *
 * A parallel (pthread based) version is obtained compiling it with _PT_PARALLEL_ defined
 *
 * Parallel parameters:
 *
 * 1) number of threads
 *
 * Distributed
 * -----------
 *
 * A distributed (MPI based) version is obtained compiling it with _PD_DISTRIBUTED_ (pulse-driven model)
 * or _ED_DISTRIBUTED_ (event-driven model) defined
 *
 * Distributed parameters:
 *
 * 1) number of donation attempts before locally terminating (#define ATTEMPTS)
 *
 * Termination:
 *
 * currently, a simplified termination detection mechanism is used. A fixed binary termination tree is determined and used
 * to propagate termination waves. In the event driven model, this same tree is used to start the computation as a
 * diffusing computation (in the sense of Dijkstra's termination algorithm).
 *
 */

#include <iostream>
#include <time.h>
#include <assert.h>
#include "MCR.h"
#include "StabSolvers.h"
#include <repository.h>
#include <Graph.h>
#include <sys/time.h>
#include <sys/resource.h>

#define MTN 16

//function that generate the nodes
//bool generated(int i);

//type of arguments used in the thread
typedef struct args{
	Graph* g;
	subproblem* current;
	subproblem* newsubp;
	int pivot;
	int curp;
	bool active;
	bool gen;
}ParrallelArgs;

//identification of the thread
pthread_mutex_t mutex;
int nts;

//the thread itself
//pthread_t* threads;

//barriers used for syncronization
//pthread_barrier_t* barrierfirst;
//pthread_barrier_t* barriersecond;

//arguments to the threads
ParrallelArgs args[MTN];


int comparator(const void* a,const void* b){
	if(a == NULL) return -1;
	if(b == NULL) return 1;
	return ((long*)a)[1] - ((long*)b)[1];
}


/*void* runParrallell(void* arg){
	pthread_mutex_lock(&mutex);
	int i = --nts;
	fflush(NULL);
	pthread_mutex_unlock(&mutex);

	while(args[i].active){
		pthread_barrier_wait(barrierfirst);

		if(args[i].pivot >= 0){
			generated(i);
		}

		pthread_barrier_wait(barriersecond);
	}
	pthread_exit(0);
}*/

MCR::MCR(int t, Graph* gh):g(gh){
	nt = t;//thread number
	nts = t;
	omp_set_num_threads(MTN < t ? MTN:t);

	//args = (ParrallelArgs**)malloc(sizeof(ParrallelArgs*)*nt);
	//threads = (pthread_t*)malloc(sizeof(pthread_t)*nt);
	//barrierfirst = (pthread_barrier_t*)malloc(sizeof(pthread_barrier_t));
	//barriersecond = (pthread_barrier_t*)malloc(sizeof(pthread_barrier_t));

	//inicialization of barrier, observe that there are nt+1 threads(the main program is itself
	// a thread and must stop at the barrier)
	//pthread_barrier_init(barrierfirst, NULL, nt+1);
	//pthread_barrier_init(barriersecond, NULL, nt+1);

	newsubp = (subproblem**)malloc(sizeof(subproblem*)*nt);

	for(int i = 0; i < nt; i++){
		newsubp[i] = (subproblem*)malloc(sizeof(subproblem));
		//args[i] = (ParrallelArgs*)malloc(sizeof(ParrallelArgs)*nt);
		args[i].pivot = -1;
		args[i].active = true;
	}
	//printf("variaveis alocadas com sucesso \n");
	//fflush(NULL);

	qmax = -1;//size of the largest clique

	subprepo = newRepo(sizeof(subproblem), g->nverts() < 100 ? g->nverts() : 100);
	doublevecrepo = newRepo(g->nverts()*sizeof(int), g->nverts() < 100 ? g->nverts() : 100);
	intvecrepo = newRepo(g->nverts()*sizeof(int), g->nverts() < 100 ? g->nverts() : 100);

	/*for(int i = 0; i < nt; i++){
		pthread_create( &(threads[i]), NULL, runParrallell , NULL);
	}*/
}

/*MCR::MCR(int t, Graph* gh, Weigth<double>* w):g(gh){
	nt = t;
	gensub = (Gen**)malloc(sizeof(Gen*)*nt);
	newsubp = (subproblem**)malloc(sizeof(subproblem*)*nt);
	for(int i = 0; i < nt; i++){
		gensub[i] = new Gen();
	}
	qmax = 0;
	subprepo = newRepo(sizeof(subproblem), g->nverts() < 100 ? g->nverts() : 100);
	doublevecrepo = newRepo(g->nverts()*sizeof(int), g->nverts() < 100 ? g->nverts() : 100);
	intvecrepo = newRepo(g->nverts()*sizeof(int), g->nverts() < 100 ? g->nverts() : 100);
}*/

MCR::~MCR(){

	//end threads
	/*for(int i = 0; i < nt; i++){
		args[i]->active = false;
		args[i]->pivot = -1;
	}

	//start the threads
	pthread_barrier_wait(barrierfirst);
	//wait for each thread finish its works
	pthread_barrier_wait(barriersecond);*/

	//release repository
	for(int i = 0; i < nt; i++){
		if(newsubp[i]!= NULL){
			release(intvecrepo, newsubp[i]->R);
			release(doublevecrepo, newsubp[i]->cover);
			release(subprepo, newsubp[i]);
		}
		//delete args[i];
		//pthread_cancel(threads[i]);
	}
	//release memory
	//delete threads;
	delete newsubp;
	//delete args;
}

subproblem*	MCR::root(){

	//memory allocation
	int* V = (int*)calloc(g->nverts(),sizeof(int));
	int* cover = (int*)calloc(g->nverts(),sizeof(int));
	int** ng = (int**)calloc(g->nverts(), sizeof(int*));
	int* d = (int*)calloc(g->nverts(), sizeof(int));
	for(int i = 0; i < g->nverts(); i++){
		ng[i] = (int*)calloc(g->nverts(), sizeof(int));
		d[i] = 0;
		for(int j = 0; j < g->nverts(); j++){
			if(g->hasEdge(i,j)&& i != j){
				ng[i][d[i]] = j;
				d[i]++;
			}
		}
	}

	Graphs::mcrSort(g, d , ng, cover);


	long order[2*g->nverts()];
	for(int i = 0; i < g->nverts(); i++){
		order[2*i] = i;
		order[(2*i)+1] = cover[i];
	}
	qsort(order, g->nverts(), 2*sizeof(long),comparator);

	for(int i = 0; i < g->nverts(); i++){
		V[i] = order[2*i];
		cover[i] = i;
	}

	subproblem* root = (subproblem*)getFromRepo(subprepo);

	//root iniciallization
	root->f = g->nverts()-1;
	root->r = g->nverts();
	root->R = V;
	root->cover = cover;
	root->q = 0;
	root->l = 0;
	root->p = root->r - 1;

	return root;
}

void MCR::generate(subproblem* currentI, subproblem** queue, int* q, long* nodes){
	//set the current problem
	current = currentI;

	int ids[g->nverts()];
	int p = current->p;
	int exp = 0;

	if(p < 0){
		release(intvecrepo, current->R);
		release(doublevecrepo, current->cover);
		release(subprepo, current);

	}else{

		//do pivotation
		int lim = nt < p? nt:p;
		for(int i = lim; i >= 0; i--){
			pivot(i, current->p , current->R, current->cover);
		}
		resort(current);

		//look for the vertices that worth
		while((exp < nt) && (p>=0)){
			if(current->l + current->cover[p] > qmax){
				ids[exp++] = p;
			}
			p--;
		}

		for(int i = 0; i < exp; i++){
			//setup
			newsubp[i] = (subproblem *) getFromRepo(subprepo);
			newsubp[i]->R = (int *) getFromRepo(intvecrepo);
			newsubp[i]->cover = (int *) getFromRepo(doublevecrepo);

			//arguments to the thread
			args[i].g = g;
			args[i].current = current;
			args[i].newsubp = newsubp[i];
			args[i].curp = ids[i];

			//do pivotation
			//pivot(ids[i], current->p , current->R, current->cover);
		}

		//reorder the vetor
		//resort(current);

		for(int i = 0; i < nt; i++){
			if(i < exp)
				args[i].pivot = current->R[ids[i]];
			else
				args[i].pivot = -1;
		}

		#pragma omp parallel for shared(args, newsubp)
		{
			for(int j = 0; j < exp; j++){
				if(args[j].curp > 0){
					int curp  = args[j].curp;//retrive the current
					int* curR = args[j].current->R;
					int Rp = args[j].pivot;//retrive the pivot
					int* R = args[j].newsubp->R;
					subproblem* newsub = args[j].newsubp;
					int* cover = args[j].newsubp->cover;
					int r;
					int i;

					args[j].gen = false;

					for (i = 0, r = 0; i < curp; i++){
						if (!g->hasEdge(curR[i], Rp))
							R[r++] = curR[i];
					}

					if (r > 0) { // new subproblem
						args[j].gen = true;
						newsub->l = args[j].current->l + 1; //g->weight(Rp);
						newsub->r = r;
						newsub->p = r - 1;
						newsub->f = 0;

						//order and sort
						int cc, fc, l;
						cover[0] = 1;
						for(i = 1; i < r; i++){
							cc = 0;
							do{
								cc++;
								fc = 1;
								for(l = 0 ; l < i; l++){
									if((!g->hasEdge(R[i], R[l])) && cover[l] == cc) fc = 0;
								}
							}while(fc == 0);
							cover[i] = cc;
							fc = 1;
							//printf("cover[%d] = %d \n", i, cover[i]);
						}
						long order[2*r];
						for(int i = 0; i < r; i++){
							order[2*i] = R[i];
							order[2*i+1] = newsub->cover[i];
						}
						qsort(order, r, 2*sizeof(long),comparator);
						for(int i = 0; i < r; i = i++){
							R[i] = order[2*i];
							newsub->cover[i] = order[2*i+1];
						}
					}
				}else args[j].gen = false;
			}
		}
		//start the threads
		//pthread_barrier_wait(barrierfirst);

		//wait for each thread finish its works
		//pthread_barrier_wait(barriersecond);

		int ind = 0;

		//update the solution known
		for(int j = 0; j < exp; j++){
			if(newsubp[j]->l > qmax){
				qmax = newsubp[j]->l;
			}
		}

		for(int j = 0; j < exp; j++){
			if((args[j].gen)&&(newsubp[j]->l + newsubp[j]->cover[newsubp[j]->p] > qmax)){
				queue[(*q)++] = newsubp[j];
				(*nodes)++;
			}else{
				release(intvecrepo, newsubp[j]->R);
				release(doublevecrepo, newsubp[j]->cover);
				release(subprepo, newsubp[j]);
			}
		}

		//update the current position
		current->p = p;

	}
}

void MCR::resort(subproblem* s){}

int MCR::numThreads(){
	return nt;
}

double	MCR::getBest(){
	return qmax + 1.0;
}

void MCR::pivot( int cand, int r, int * R, int* cover) {}

/*bool generated(int j){

	if(args[j].curp < 0)return false;

	Graph* g = args[j].g;
	int curp  = args[j].curp;//retrive the current
	int* curR = args[j].current->R;
	int Rp = args[j].pivot;//retrive the pivot
	int* R = args[j].newsubp->R;
	subproblem* newsub = args[j].newsubp;
	int r;
	int i;

	args[j].gen = false;

	for (i = 0, r = 0; i < curp; i++){
		if (!g->hasEdge(curR[i], Rp))
			R[r++] = curR[i];
	}

	if (r > 0) { // new subproblem
		args[j].gen = true;
		newsub->l = args[j].current->l + 1; //g->weight(Rp);
		newsub->r = r;
		newsub->p = r - 1;
		newsub->f = 0;

		//order and sort

		Graph* gh = g->homomorphism(r, R);
		Graphs::greedyCoverSort(gh ,r, newsub->cover);

		long order[2*r];
		for(int i = 0; i < r; i++){
			order[2*i] = R[i];
			order[2*i+1] = newsub->cover[i];
		}
		qsort(order, r, 2*sizeof(long),comparator);
		for(int i = 0; i < r; i = i++){
			R[i] = order[2*i];
			newsub->cover[i] = order[2*i+1];
		}

		delete gh;
		return true;
	}

	return false;
}*/

